package LFUCache;

import java.util.*;

public class Solution {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    class LFUCache {
        private static class Node {
            int key, value, freq = 1; // 新书只读了一次
            Node prev, next;

            Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        private final int capacity;
        private final Map<Integer, Node> keyToNode = new HashMap<>();
        private final Map<Integer, Node> freqToDummy = new HashMap<>();
        private int minFreq;

        public LFUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            Node node = getNode(key);
            return node != null ? node.value : -1;
        }

        public void put(int key, int value) {
            Node node = getNode(key);
            if (node != null) { // 有这本书
                node.value = value; // 更新 value
                return;
            }
            if (keyToNode.size() == capacity) { // 书太多了
                Node dummy = freqToDummy.get(minFreq);
                Node backNode = dummy.prev; // 最左边那摞书的最下面的书
                keyToNode.remove(backNode.key);
                remove(backNode); // 移除
                if (dummy.prev == dummy) { // 这摞书是空的
                    freqToDummy.remove(minFreq); // 移除空链表
                }
            }
            node = new Node(key, value); // 新书
            keyToNode.put(key, node);
            pushFront(1, node); // 放在「看过 1 次」的最上面
            minFreq = 1;
        }

        private Node getNode(int key) {
            if (!keyToNode.containsKey(key)) { // 没有这本书
                return null;
            }
            Node node = keyToNode.get(key); // 有这本书
            remove(node); // 把这本书抽出来
            Node dummy = freqToDummy.get(node.freq);
            if (dummy.prev == dummy) { // 抽出来后，这摞书是空的
                freqToDummy.remove(node.freq); // 移除空链表
                if (minFreq == node.freq) { // 这摞书是最左边的
                    minFreq++;
                }
            }
            pushFront(++node.freq, node); // 放在右边这摞书的最上面
            return node;
        }

        // 创建一个新的双向链表
        private Node newList() {
            Node dummy = new Node(0, 0); // 哨兵节点
            dummy.prev = dummy;
            dummy.next = dummy;
            return dummy;
        }

        // 在链表头添加一个节点（把一本书放在最上面）
        private void pushFront(int freq, Node x) {
            Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
            x.prev = dummy;
            x.next = dummy.next;
            x.prev.next = x;
            x.next.prev = x;
        }

        // 删除一个节点（抽出一本书）
        private void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
        }
    }
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int index = 0,i = 0,j = 0,n = nums1.length,m = nums2.length;
        int[] ans = new int[n+m];
        while (i<n&&j<m){
            if(nums1[i]<nums2[j]) {
                i++;
            } else if (nums1[i]>nums2[j]) {
                j++;
            } else {
                ans[index++] = nums1[i];
                i++;
                j++;
            }
        }
        return Arrays.copyOfRange(ans,0,index);
    }
    public boolean isSubsequence(String s, String t) {
//        int i = 0,j = 0,n = s.length(),m = t.length();
//        while (i<n&&j<m) {
//            if(t.charAt(j) == s.charAt(i)) {
//                i++;
//            }
//            j++;
//        }
//        return i == n;

        // 动态规划
        // dp[i][j] 表示t中从i位置开始后字符j第一次出现的位置
        // dp[i][j] = i (t.charAt(i) == j+'a')
        // dp[i][j] = dp[i+1][j] (t.charAt(i) != j+'a')
        int m = t.length(), n =s.length();
        int[][] dp = new int[m+1][26];
        for (int i = 0; i < 26; i++) {
            dp[m][i] = m;
        }
        for (int i = m-1; i >=0 ; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) == j + 'a')
                    dp[i][j] = i;
                else
                    dp[i][j] = dp[i + 1][j];
            }
        }
        // 得到dp数组之后
        int add = 0; // 索引 索引应该递增的
        for (int i = 0; i < n; i++) {
            if (dp[add][s.charAt(i)-'a'] == m) {
                return false;
            }
            add = dp[add][s.charAt(i)-'a']+1;
        }
        return true;
    }
    public int findContentChildren(int[] g, int[] s) {
        // 双指针+贪心
        // 大饼干满足大胃口
        Arrays.sort(g);
        Arrays.sort(s);
        int i = g.length-1,j = s.length-1;
        while (i>=0&&j>=0) {
            if (s[j] >= g[i]) {
                j--;
            }
            i--;
        }
        return s.length-j-1;
    }
    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        for (int i = 0;i<chars.length;i+=2*k) {
            int start = i;
            int end = Math.min(chars.length-1,start+k-1);
            reverse(chars,start,end);
        }
        return new String(chars);
    }
    private void reverse(char[] s,int start,int end) {
        int i = start,j = end;
        while (i<j) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
            i++;
            j--;
        }
    }
    public boolean findTarget(TreeNode root, int k) {
        // 二叉搜索树
        // 双指针
        List<Integer> list = new ArrayList<>();
        insertToList(root,list);
        int i = 0,j = list.size()-1;
        while (i<j) {
            if(list.get(i) + list.get(j) < k) {
                i++;
            } else if (list.get(i) + list.get(j) > k) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
    private void insertToList(TreeNode root,List<Integer> list){
        if(root == null) {
            return;
        }
        insertToList(root.left,list);
        list.add(root.val);
        insertToList(root.right,list);
    }
    public int countBinarySubstrings(String s) {
        //
        int ptr = 0, n = s.length(), last = 0, ans = 0;
        while (ptr < n) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;
            }
            ans += Math.min(count, last);
            last = count;
        }
        return ans;
    }
    public int[][] flipAndInvertImage(int[][] image) {
        for (int[] ima: image) {
            int l = 0,r = ima.length-1;
            while (l<=r) {
                int t = ima[l];
                ima[l] = ima[r] == 0?1:0;
                ima[r] = t == 0? 0:1;
                l++;
                r--;
            }
        }
        return image;
    }
    public int[] shortestToChar(String s, char c) {
        int[] ans = new int[s.length()];
        for (int i = 0,index = -s.length(); i < s.length(); i++) {
            if(s.charAt(i) == c) {
                index = i;
            }
            ans[i] = i-index;
        }
        for (int i = s.length()-1,index = s.length()*2; i >=0 ; i--) {
            if(s.charAt(i) == c) {
                index = i;
            }
            ans[i] = Math.max(ans[i],index-i);
        }
        return ans;
    }
    public ListNode middleNode(ListNode head) {
        //
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null&&fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public int[] sortArrayByParity(int[] nums) {
        int i = 0;
        int j = nums.length-1;
        while (i<j) {
            if(nums[i]%2!=0) {
                i++;
            } else if (nums[j]%2 == 0) {
                j--;
            } else {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] =t;
                i++;
                j--;
            }
        }
        return nums;
    }
    public String reverseOnlyLetters(String s) {
        int i = 0,j = s.length()-1;
        char[] chars = s.toCharArray();
        while (i<j) {
            if(!Character.isLetter(s.charAt(i))) {
                i++;
            } else if (!Character.isLetter(s.charAt(j))) {
                j--;
            } else {
                char c = chars[i];
                chars[i] = chars[j];
                chars[j] = c;
            }
        }
        return new String(chars);
    }
    public int[] diStringMatch(String s) {
        // 贪心
        int i = 0,j = s.length();
        int[] ans = new int[s.length()+1];
        for (int k = 0; k < s.length(); k++) {
            if(s.charAt(k) == 'I') {
                ans[k] = i++;
            } else {
                ans[k] = j--;
            }
        }
        ans[ans.length-1] = i;
        return ans;
    }
    public boolean isLongPressedName(String name, String typed) {
        int i = 0,j = 0;
        int n = typed.length(),m = name.length();
        while (j<n){
            if(i<m&&name.charAt(i) == typed.charAt(j)) {
                i++;
                j++;
            } else if (j>0&&typed.charAt(j) == typed.charAt(j-1)) {
                // 可能按重复了
                j++;
            } else {
                return false;
            }
        }
        return i == m;
    }
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        int index = nums.length-1,i = 0,j = nums.length-1;
        while (i<=j) {
            if(Math.abs(nums[i]) > Math.abs(nums[j])) {
                ans[index--] = nums[i]*nums[i++];
            } else {
                ans[index--] = nums[j]*nums[j--];
            }
        }
        return ans;
    }
}
